package hot100;


/*
 * Author：江松
 * Date：2023/4/15 10:27
 *
 寻找2个正序数组的中位数，O(log(n+m))
 1,合并，O(n+m)
 2,不合并，因为下标已经确定，中位数下标就确定了，可以使用双指针
 遍历到len/2即可，因为已经选出了一半;然后分奇数偶数讨论即可
 维护l，r表示2个中间的值
 题解：
 2,O(log(n+m))只有二分才能达到这个复杂度

 */

public class Main4 {




    public double findMedianSortedArrays(int[] A, int[] B) {
        int n=A.length,m=B.length;
        int a=0,b=0;
        int len=(m+n)>>1;
        int l=-1,r=-1;
        for(int i=0;i<=len;++i){
            l=r;
            if(a<n&&(b>=m||A[a]<=B[b])){
                r=A[a++];
            }else{
                r=B[b++];
            }
        }
        if(((m+n)&1)!=0){
            return r;
        }else return (double) (l+r)/2;
    }

}
